def kmp_search(string, patt):
    next = build_next(patt)
    i = 0
    j = 0
    while i <len(string):
        print(i)
        if string[i] == patt[j]:

            i += 1
            j += 1
        elif j > 0:
            j = next[j - 1]
        else:
            i += 1
        if j == len(patt):
            return i - j


def build_next(patt):
    next = [0, 1, 1, 2, 2]
    return next


print(kmp_search('abaaabaaabaaabaaabaaabaaabaac', 'abaac'))

'''abaaabaaabaaabaaabaaabaaabaac'''
'''    abaac'''